1. Field of the Invention
The present invention relates generally to electronic communication via switch fabrics. More specifically, the present invention relates to extending fat tree networks into a third dimension and adding mechanisms to PCIe switches so that they may operate as part of these extended fat tree networks.
2. Description of the Related Art
The fat tree network, is a universal network for provably efficient communications. Unlike an ordinary computer scientist's notion of a tree, which has “skinny” links all over, the links in a fat-tree become “fatter” as one moves up the tree towards the root. A Clos network can be seen to be a fat tree when it is drawn in a folded fashion. Fat tree networks, including Clos networks, are an efficient means (in terms of the number of switches required) of providing non-blocking communications among large numbers of nodes. A Clos network can also be extended to additional stages, retaining its optimality and non-blocking ability. Fat trees are used because they can be made non-blocking and because they are efficient. The 3 stage folded Clos network can be extended to 5 stages to form the well known Benes network, and a 5-stage Benes network may be extended to a 7-stage Cantor network, retaining the fat tree properties.
Clos networks have three stages: the ingress stage, middle stage, and the egress stage. Each stage is made up of a number of switches. Each communication entering an ingress switch can be routed through any of the available middle stage switches, to the relevant egress switch. A middle stage switch is available for a particular new communication if both the link connecting the ingress switch to the middle stage switch, and the link connecting the middle stage switch to the egress switch, are free.
FIG. 1 depicts an example Clos network. This is a simple example of a non-blocking 3-stage switch fabric, but the principles illustrated work for Clos networks and other fat tree networks composed of any numbers of ports and switches.
The Peripheral Component Interface (PCI) was a communication standard utilizing parallel busses to connect devices in a computer system topology. While it was extremely popular in its day, it has largely been supplanted by the newer PCI Express (PCIe) standard, which replaces the parallel bus system with a serial, point-to-point scheme.
PCIe switches can be implemented in a Clos network configuration. Some problems with such a configuration, however, are that PCIe switch fabrics are limited in scalability by the size of the PCIe 8-bit BUS name space and they are limited in their ability to spread traffic evenly over redundant links by address and ID routing rules and producer-consumer ordering rules.
What is needed is a solution that does not suffer from these drawbacks.